/// 存储第n项斐波那契数的结构体
pub struct Fibonacci {
    n: u32,
}

impl Fibonacci {
    /// 实例化
    ///
    /// # Examples
    ///
    /// ```
    /// use fibonacci::Fibonacci;
    ///
    /// let f = Fibonacci::new(8);
    /// ```
    pub fn new(n: u32) -> Self {
        Self { n }
    }

    /// 迭代法
    ///
    /// # Examples
    ///
    /// ```
    /// use fibonacci::Fibonacci;
    ///
    /// let f = Fibonacci::new(8);
    /// assert_eq!(21, f.iterative());
    /// ```
    pub fn iterative(&self) -> u64 {
        match self.n {
            0 => 0,
            1 => 1,
            _ => {
                let (mut a, mut b) = (0, 1);
                for _ in 1..self.n {
                    let next = a + b;
                    a = b;
                    b = next;
                }
                b
            }
        }
    }

    /// 递归法
    ///
    /// **警告：当n>40时，效率极低！**
    ///
    /// # Examples
    ///
    /// ```
    /// use fibonacci::Fibonacci;
    ///
    /// let f = Fibonacci::new(8);
    /// assert_eq!(21, f.recursive());
    /// ```
    pub fn recursive(&self) -> u64 {
        Self::recursive_fib(self.n)
    }

    fn recursive_fib(n: u32) -> u64 {
        match n {
            0 => 0,
            1 => 1,
            _ => Self::recursive_fib(n - 1) + Self::recursive_fib(n - 2),
        }
    }

    /// 记忆化递归法
    ///
    /// # Examples
    ///
    /// ```
    /// use fibonacci::Fibonacci;
    ///
    /// let f = Fibonacci::new(8);
    /// assert_eq!(21, f.memoized_recursive());
    /// ```
    pub fn memoized_recursive(&self) -> u64 {
        match self.n {
            0 => 0,
            1 => 1,
            _ => {
                let mut memo = vec![None; (self.n + 1) as usize];
                memo[0] = Some(0);
                memo[1] = Some(1);
                Self::memoized_fib(self.n, &mut memo)
            }
        }
    }

    fn memoized_fib(n: u32, memo: &mut Vec<Option<u64>>) -> u64 {
        if let Some(val) = memo[n as usize] {
            return val;
        }

        let result = Self::memoized_fib(n - 1, memo) + Self::memoized_fib(n - 2, memo);
        memo[n as usize] = Some(result);
        result
    }
}
